home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 15147 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.2 KB
  1. Path: in1.uu.net!zdc!zippo!drn
  2. From: Clarence Chiang
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: Can I do it recursively?
  5. Date: 3 Apr 1996 12:48:22 -0800
  6. Organization: Zippo
  7. Sender: http@doc.zippo.com
  8. Message-ID: <4juo6m$n6i@doc.zippo.com>
  9. NNTP-Posting-Host: doorstop.spiderisland.com
  10.  
  11. In article <4jrcqj$3s1@nuscc.nus.sg>, eng50636@leonis.nus.sg says...
  12. >
  13. >Hi,
  14. >
  15. >  I am doing a program of a famous problem(forget the name, sorry). It is 
  16. >
  17. >about how a horse can travel through the whole 8x8 chess board,without 
  18. >
  19. >repeating any position that has been travelled(may seem to easy for 
  20. >
  21. >experts---I am only a beginner). I want to do it by recursion. But it 
  22. >
  23. >seems quite impossible since the run-time is too long. 
  24. >
  25. >  I just want to know whether there is a good method that can give me the
  26. >
  27. >answer by means of some checking to reduce the possibilities. Is it
  28. >
  29. >possible? (Again, need to be done recursively.) 
  30. >
  31. >  Any help is appreciated!!!  
  32. >
  33. >                
  34.  
  35. I don't think it is a question of whether the problem can be solved recursively
  36. or iteratively. It is just that this problem is one of those NP-complete problem,
  37. which requires exponential amount of time as the problem size grows.
  38.  
  39. Clarence Chiang
  40. Spider Island Software
  41.  
  42.